package n_02;

import java.util.List;

/**
 * @author ChengMiao
 * @date 2021/6/28 13:58
 * @Desc No.2 两数相加
 * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 */
public class Demo {

    public static void main(String[] args) {
        ListNode node_01 = new ListNode(9,new ListNode(9,new ListNode(9,new ListNode(9,new ListNode(9,new ListNode(9,new ListNode(9)))))));
        ListNode node_02 = new ListNode(9,new ListNode(9,new ListNode(9,new ListNode(9))));

        ListNode node = addTwoNumbers(node_01, node_02);

        while(node!=null){
            System.out.println(node.val);
            node = node.next;
        }

    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        // [2,4,3]
        // [5,6,4]
        // [7,0,8]

            //  999999
            //  9999
            //  8999001
            ListNode header = null;
            ListNode tail = null;
            int carry = 0;  // 标识是否进位

            // 同时遍历两个链表，直至两个链表都遍历完成
            // 思路: 将统一索引的值相加取个位数保存,如果相加值有进位则保存至下一次遍历时加一,以此类推，直至所有链表遍历完成
            // 不足位的链表默认取0
            while(l1!=null || l2!=null){
                int n1 = l1==null?0:l1.val;
                int n2 = l2==null?0:l2.val;

                int sum = n1 + n2 + carry;

                if(header==null){
                    header = tail = new ListNode(sum%10);
                }else{
                    tail.next = new ListNode(sum%10);
                    tail = tail.next;
                }

                carry = sum/10;

                if(l1!=null){
                    l1 = l1.next;
                }
                if(l2!=null){
                    l2 = l2.next;
                }
            }

            if(carry>0){
                tail.next = new ListNode(carry);
            }

            return header;

    }
}
